package lc66;
//给定一个由 整数 组成的 非空 数组所表示的非负整数，在该数的基础上加一。
//
// 最高位数字存放在数组的首位， 数组中每个元素只存储单个数字。
//
// 你可以假设除了整数 0 之外，这个整数不会以零开头。
//
//
//
// 示例 1：
//
//
//输入：digits = [1,2,3]
//输出：[1,2,4]
//解释：输入数组表示数字 123。
//
//
// 示例 2：
//
//
//输入：digits = [4,3,2,1]
//输出：[4,3,2,2]
//解释：输入数组表示数字 4321。
//
//
// 示例 3：
//
//
//输入：digits = [0]
//输出：[1]
//
//
//
//
// 提示：
//
//
// 1 <= digits.length <= 100
// 0 <= digits[i] <= 9
//
// Related Topics 数组 数学 👍 828 👎 0

import utils.IntArrOneFactory;

import java.util.Arrays;

//leetcode submit region begin(Prohibit modification and deletion)
class Solution {

    /**
     * 66. 加一
     * 难度：简单
     * time:O(n) n为数组长度
     * space:O(1) 最多额外存一个空间
     * spend: 12m
     */
    public int[] plusOne(int[] digits) {
        // 从最后一个数字开始加，如果加了以后对10取余不等于0，说明不需要进位，直接返回就行
        for(int i = digits.length - 1; i >= 0; i--){
            digits[i] += 1;
            digits[i] %= 10;
            if(digits[i] % 10 != 0){
                return digits;
            }
        }
        // 如果前面全部进位，也就是999变成了000，那只需要建一个长度为len+1的数组，然后首位赋值1即可。
        digits = new int[digits.length + 1];
        digits[0] = 1;
        return digits;
    }

    public static void main(String[] args) {
        IntArrOneFactory ing = new IntArrOneFactory();
        int[] produce = ing.produce("[9,9,9,9]");
        int[] ints = new Solution().plusOne(produce);
        System.out.println(Arrays.toString(ints));

    }

}
//leetcode submit region end(Prohibit modification and deletion)